#! /opt/local/bin/perl5.12.3

use strict;
use warnings;

use GraphViz;
use Astar;
open P2TXT, "> city_conns.txt";
select P2TXT;


# Build routes from cities;
exit if scalar @ARGV != 2;
my ($nCols, $nRows) = (@ARGV[0, 1]);
# Amount of cities
my $city_n = $nCols;
my $costRandLim = 10;

my @cities;
my %cityConnections;

# Meaningful indexes
my ($cityName, $cityCoords) = (0, 1);
my ($coordX, $coordY) = (0, 1);
my @graph;

sub buildCitiesList {
    @_ or return 0;
    my $n = shift;
    my ($randx, $randy);
    for ( 1 .. $n ) {
        ($randx, $randy) = ( int(rand($nCols)), int(rand($nRows)) );
        push @cities, [ ((length $_ == 1) ? "City_0$_" : "City_$_"), [$randx, $randy]];
    }
    return 1;
}

sub buildHash {
    @_ or return 0;
    my ($cities) = shift;
    foreach (@$cities) {
        if ( not exists $cityConnections{$_->[$cityName]} ) {
            $cityConnections{$_->[$cityName]} = [];
        }
    }
    return 1;
}

sub buildRandomEdges {
    @_ or return 0;
    my ($cities, $cityConnections) = @_;
    my ($rand_city, $rand_city_name);
    for ( sort{ length $a <=> length $b || $a cmp $b } keys %cityConnections ) {
        my $rf = rand($city_n);
        for ( my $i = 0; $i < $rf; $i++ ) {
            $rand_city = int rand @$cities;
            $rand_city_name = $cities->[$rand_city][0];
            $rand_city_name ne $_ or next;
            #                             Push [City coords, random city cost, City name]
            push @{ $cityConnections{$_} }, [$cities->[$rand_city][$cityCoords], int(rand($costRandLim)), $cities->[$rand_city][$cityName]]
                unless grep{ $rand_city_name eq $_->[2] } @{ $cityConnections{$_} };
        }
    }
    return 1;
}

sub buildGraph {
    @_ or return 0;
    my ($cityConnections) = shift;
    my $g = GraphViz->new();
    $g->add_node($_) for keys %$cityConnections;

    for my $city ( keys %$cityConnections ) {
        $g->add_edge($city, $_->[2], dir => 'forward', label => $_->[1] ) for @{ $cityConnections->{$city} };
    }

    return $g;
}

# Matrix representation
sub printMatrixRepresentation {
    @_ or return 0;
    my ($cities, $cityConnections) = @_;

    # Begin
    print "\nCITY CONNECTIONS\n\n";

    # Fill graph / connections
    print "   ";
    (length $_ == 1) ? print "  $_" : print " $_" for 1..$#{$cities}+1;
    print "\n";
    for my $cityy ( 1..$#{$cities}+1 ) {
        (length $cityy == 2 ) ? print " $cityy" : print "  $cityy";
        for my $cityx ( @$cities ) {
            if ( $cities->[$cityy-1][$cityName] eq $cityx->[$cityName] ) {
                print "  0";
            }
            elsif ( grep{ $cityx->[$cityName] eq $_->[2] } @{ $cityConnections->{$cities->[$cityy-1][$cityName]} } ) {
                print "  x";
            } else { print "  .";}
        }
        print "\n";
    }

    # End
    print "\nTable End\n\n";
}

sub printAdjacencyList {
    my ($cities, $cityConnections) = (@_);
    for my $cityKey ( sort{ length($a) <=> length($b) || $a cmp $b } keys %$cityConnections ) {
        print "$cityKey connections to: ";
        for my $cityProps ( sort{ length($a->[$cityName]) <=> length($b->[$cityName]) ||
                          $a->[$cityName] cmp $b->[$cityName] } @{$cityConnections->{$cityKey}} ) {

            printf("%9s", $cityProps->[2]);
        }
        print "\n";
    }
}

# Build Data
buildCitiesList($city_n) or die "Unexpected error at \&buildCitiesList\n";
buildHash(\@cities) or die  "Unexpected error at \&buildHash\n";
buildRandomEdges(\@cities, \%cityConnections) or die "Unexpected error at \&buildRandomEdges\n";

# Print matrix representation of directed graph.  Each x represents a forward edge from row(vertexA) to col(vertexB)
printMatrixRepresentation(\@cities, \%cityConnections);

# Print adjacency list
printAdjacencyList(\@cities, \%cityConnections);

# Build Data Structure
my $graph = buildGraph(\%cityConnections);
$graph->as_png("graph.png"); # Print directed graph; vertex = city


# Compute sol.
my $goal = $cities[ int(rand($city_n)) ];
my $root = $cities[0];

my ($plan, $cost) = Astar::uniformCostSearch(\%cityConnections, \@cities, $root, $goal);

print STDOUT "Plan from $root->[$cityName] to $goal->[$cityName]: ";
for my $i ( 0.. $#{$plan} ) {
    print STDOUT "([$plan->[$i][0], $plan->[$i][1]], $plan->[$i][2]) ";  }
print STDOUT "\n";
print STDOUT "Total cost: $cost\n";
